package DynamicProgramming;

import java.util.Scanner;

public class 完全背包 {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int m=sc.nextInt();//背包容量
        int n=sc.nextInt();//物品个数
        int[] w=new int[n];
        int[] v=new int[n];
        for (int i = 0; i < n; i++) {
            w[i]=sc.nextInt();
            v[i]=sc.nextInt();
        }
        int[] dp=new int[m+1];//一维：背包容量为i时的最大值
        for (int i = 0; i < n; i++) {
            for (int j =w[i]; j <=m ; j++) {
                dp[j]=Math.max(dp[j-w[i]]+v[i],dp[j]);
            }
        }
        System.out.println(dp[m]);//最大价值
    }
}
